package ljl.codetop;

import commons.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

public class _98_is_valid_bst {

    /**
     * 一次过，而且我的解法也比较简单，good
     */
    public static class have_a_try {

        TreeNode prev;
        public boolean isValidBST(TreeNode root) {
            if (root == null) return true;
            boolean left = isValidBST(root.left);
            if (!left)
                return false;
            if (prev != null && prev.val >= root.val)
                return false;
            prev = root;
            return isValidBST(root.right);
        }
    }

    /**
     * 比我的优雅
     */
    static class off1 {
        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }

        public boolean isValidBST(TreeNode node, long lower, long upper) {
            if (node == null) {
                return true;
            }
            if (node.val <= lower || node.val >= upper) {
                return false;
            }
            return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
        }
    }

    static class off2 {
        public boolean isValidBST(TreeNode root) {
            Deque<TreeNode> stack = new LinkedList<>();
            long preValue = Long.MIN_VALUE;

            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (root.val <= preValue) {
                    return false;
                }
                preValue = root.val;
                root = root.right;
            }
            return true;
        }
    }

    static class copy_off2 {
        public boolean isValidBST(TreeNode root) {
            LinkedList<TreeNode> q = new LinkedList<>();
            long prev = Long.MIN_VALUE;
            while (!q.isEmpty() || root != null) {
                while (root != null) {
                    q.push(root);
                    root = root.left;
                }
                root = q.pop();
                if (prev >= root.val) return false;
                prev = root.val;
                root = root.right;
            }
            return true;
        }
    }

}
